/**
 * 
 */
package uk.ac.manchester.cs.graph;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author Pavel Klinov
 *
 * pklinov@cs.man.ac.uk, pklinov@clarkparsia.com
 * 
 * 27 Apr 2010
 */
public class DirectedGraphImpl<V,E> implements DirectedGraph<V,E> {
	//outgoing edges
	private Map<V, Set<Edge<V, E>>> m_vertexMap = new HashMap<V, Set<Edge<V, E>>>();
	//incoming edges
	private Map<V, Set<Edge<V, E>>> m_invVertexMap = new HashMap<V, Set<Edge<V, E>>>();
	//Identity map, TODO Figure out a better solution
	private Map<V,V> m_idVertexMap = new HashMap<V,V>();
	private Set<V> m_roots = new HashSet<V>();
	
	public boolean isDirected() {
		return true;
	}	
	
	private V findVertex(V vertex) {
		V stored = m_idVertexMap.get(vertex);
		
		return stored == null ? vertex : stored;
	}
	
	public Edge<V, E> addEdge(E object, V start, V end) {

		Edge<V, E> edge = null;
		
		if (!m_vertexMap.containsKey(start) || null == (edge = findEdge( start, end ))) {
			
			start = findVertex(start);
			end = findVertex(end);
			edge = new EdgeImpl<V, E>(object, start, end);
			
			addVertex(start);
			addVertex(end);
			getIncidentEdges( start ).add( edge );
			getIncomingEdges( end ).add( edge );
			
			if (m_roots != null) m_roots.remove( end );
		}
		
		return edge;
	}
	
	public Set<Edge<V, E>> getIncidentEdges(V vertex) {
		return m_vertexMap.get( vertex );
	}
	
	public Set<Edge<V, E>> getIncomingEdges(V vertex) {
		return m_invVertexMap.get( vertex );
	}
	
	public void addVertex(V vertex) {
		V stored = m_idVertexMap.get(vertex);
		
		if (stored == null) {
			
			m_vertexMap.put( vertex, new HashSet<Edge<V, E>>() );
			m_invVertexMap.put( vertex, new HashSet<Edge<V, E>>() );
			m_idVertexMap.put(vertex, vertex);
			
			if (m_roots != null) m_roots.add( vertex );
		}
	}

	public Set<V> getAdjacentVertices(V vertex) {

		Set<Edge<V, E>> incidentEdges = getIncidentEdges( vertex );
		
		if (incidentEdges != null) {
			
			Set<V> neighbors = new HashSet<V>();
			
			for (Edge<V, E> incident : incidentEdges) {
				
				neighbors.add( incident.getEnd() );
			}
			
			return neighbors;
		}
	
		return null;
	}

	public Set<V> getVertices() {
		return new HashSet<V>(m_vertexMap.keySet());
	}

	public void removeVertex(V vertex) {
		if (!m_idVertexMap.containsKey(vertex)) return;

		//Remove inbound edges
		for (Edge<V,E> incoming : m_invVertexMap.get(vertex)) {
			Set<Edge<V,E>> outbound = getIncidentEdges(incoming.getStart());
			
			outbound.remove(incoming);
		}
		//Remove outbound edges
		for (Edge<V,E> outbound : m_vertexMap.get(vertex)) {
			Set<Edge<V,E>> incoming = getIncomingEdges(outbound.getEnd());
			
			incoming.remove(outbound);
		}
		
		m_invVertexMap.remove(vertex);
		m_vertexMap.remove( vertex );
		m_idVertexMap.remove(vertex);
		
		if (m_roots != null) m_roots.remove( vertex );
	}

	public void removeEdge(Edge<V, E> edge) {
		getIncidentEdges( edge.getStart() ).remove( edge );
		getIncomingEdges(edge.getEnd()).remove(edge);
		m_roots = null;
	}
	
	public Edge<V, E> findEdge(V start, V end) {
		
		for (Edge<V, E> incident : getIncidentEdges( start )) {
			
			if ((incident.getEnd().equals( end ) && incident.getStart().equals( start ))) {
				
				return incident;
			}
		}
		
		return null;
	}

	@Override
	public Set<V> getRoots() {
		
		return m_roots != null ? m_roots : discoverRoots();
	}

	private Set<V> discoverRoots() {

		m_roots = new HashSet<V>(m_vertexMap.keySet());
		
		for (V vertex : m_vertexMap.keySet()) {
			
			for (Edge<V,E> edge : getIncidentEdges(vertex)) {
				
				m_roots.remove(edge.getEnd());
			}
		}
		
		return m_roots;
	}
}
